Relational models of knowledge, such as a graph-based data store, can be used to provide answers to search queries. Such models describe real-world entities (people, places, things) and facts about these entities in the form of graph nodes and edges between the nodes. While such graphs may represent a significant amount of facts, even the largest graphs may be missing tens of millions of entities, or may have incorrect facts for some of the entities. For example, dates or other attributes can often be missing for a given entity.